
#include "stdafx.h"
//#include "ap\ap_comm.h"
//#include "ds\ds_allocator.h"

#define osAllocPage() (BYTE *)malloc(OS_PAGE_SIZE)
#define osFreePage(PTR) free(PTR)

namespace ds {

FIXED_SIZE_ALLOCATOR FixedAlloc;

/******************************************************************************/
/* ds::FIXED_SIZE_ALLOCATOR::~FIXED_SIZE_ALLOCATOR
/*
/******************************************************************************/
FIXED_SIZE_ALLOCATOR::~FIXED_SIZE_ALLOCATOR(void)
{
   for (int k = 0; k < pools.Length(); ++k) {
      POOL & pool = pools[k];

      for (int i = 0; i < pool.chunks.Length(); ++i) {
         CHUNK & chunk = pool.chunks[i];

         STRONG_ASSERT3(chunk.empty == pool.itemsPerChunk, i, chunk.empty, pool.itemsPerChunk);
         _FreeChunk(chunk);
      }
   }
}

/******************************************************************************/
/* ds::FIXED_SIZE_ALLOCATOR::POOL::PrepareNextChunk
/*
/******************************************************************************/
void FIXED_SIZE_ALLOCATOR::POOL::PrepareNextChunk(void)
{
   if (chunks.IsEmpty()) {
      return ;
   }

   int index = 0; 
   int empty = chunks[0].empty;
   for (int k = 0; k < chunks.Length(); ++k) {
      CHUNK & cur = chunks[k];
      if (empty > cur.empty) {
         empty = cur.empty;
         index = k;
      }
   }

   if (index != 0) {
      // move it to first element
      dsSwap(chunks[0], chunks[index]);
   }
}

/******************************************************************************/
/* ds::FIXED_SIZE_ALLOCATOR::_Alloc
/*
/******************************************************************************/
void * FIXED_SIZE_ALLOCATOR::_Alloc(int size)
{
   osLOCKER locker(lock);

   size = max(size, sizeof(ITEM));

   POOL * pool = NULL;

   for (int i = 0; i < pools.Length(); ++i) {
      if (pools[i].itemSize == size) {
         pool = &pools[i];
         break;
      }
   }

   CHUNK * chunk = NULL;

   if (pool == NULL) {
      // create new pool for specific size
      POOL newPool;
      newPool.itemSize        = size;
      newPool.itemsPerChunk   = OS_PAGE_SIZE / size;

      _AllocChunk(newPool);

      pools += newPool;
      pool  = &pools.Back();
      pool->empty += pool->itemsPerChunk;
      chunk = &pool->chunks.Back();
   } else if (pool->empty == 0) {
      // all chunks are full, allocate new
      chunk = _AllocChunk(*pool);
      pool->empty += pool->itemsPerChunk;
   } else {
      STRONG_ASSERT1(pool->chunks[0].empty > 0, pool->chunks[0].empty);
      chunk = &pool->chunks[0];
   }

   STRONG_ASSERT5(pool->allocated + pool->empty == pool->itemsPerChunk * (pool->chunks.Length() + pool->fullChunks.Length()), pool->allocated, pool->empty, pool->itemsPerChunk, pool->chunks.Length(), pool->fullChunks.Length());

   STRONG_ASSERT(chunk != NULL);
   STRONG_ASSERT(chunk->freeItem != NULL);

   ITEM * item = chunk->freeItem;
   chunk->freeItem = item->next;

   ++pool->allocated;
   --pool->empty;
   --chunk->empty;

   // this chunk is full, move it to the fullChunks array and find other most used chunk
   if (chunk->empty == 0) {
      pool->fullChunks += *chunk;
      pool->chunks.EraseNonSorted(chunk - pool->chunks.Begin());

      pool->PrepareNextChunk();
   }

   return item;
}

/******************************************************************************/
/* ds::FIXED_SIZE_ALLOCATOR::CHUNK::IsBelong
/*
/******************************************************************************/
bool FIXED_SIZE_ALLOCATOR::CHUNK::IsBelong(void * ptr, POOL * pool) const
{
   bool res = data <= (BYTE *)ptr && data + pool->itemsPerChunk * pool->itemSize > (BYTE *)ptr;

   STRONG_ASSERT4(!res || ((BYTE *)ptr - data) % pool->itemSize == 0, ptr, data, pool->itemSize, pool->itemsPerChunk);
   return res;
}

typedef ds::FIXED_SIZE_ALLOCATOR::CHUNK CHUNK_T;

/******************************************************************************/
/* ds::_FindChunk
/*
/******************************************************************************/
CHUNK_T * FIXED_SIZE_ALLOCATOR::POOL::FindChunk(dsVECTOR<CHUNK_T> & chunks, void * ptr)
{
   for (int i = 0; i < chunks.Length(); ++i) {
      CHUNK_T & cur = chunks[i];
      if (cur.IsBelong(ptr, this)) {
         return &cur;
      }
   }

   return NULL;
}

/******************************************************************************/
/* ds::FIXED_SIZE_ALLOCATOR::_Free
/*
/******************************************************************************/
void FIXED_SIZE_ALLOCATOR::_Free(void * ptr, int size)
{
   osLOCKER locker(lock);

   size = max(size, sizeof(ITEM));

   POOL * pool = NULL;
   for (int i = 0; i < pools.Length(); ++i) {
      if (pools[i].itemSize == size) {
         pool = &pools[i];
         break;
      }
   }

   STRONG_ASSERT2(pool != NULL, ptr, size);

   CHUNK * chunk = pool->FindChunk(pool->chunks, ptr);

   if (chunk == NULL) {
      chunk = pool->FindChunk(pool->fullChunks, ptr);
   }

   STRONG_ASSERT2(chunk != NULL, ptr, size);

   ITEM * item = (ITEM *)ptr;
   item->next = chunk->freeItem;
   chunk->freeItem = item;

   --pool->allocated;
   ++pool->empty;
   ++chunk->empty;

   if (chunk->empty == 1) {
      // chunk was full, move it to chunks array
      pool->chunks += *chunk;
      pool->fullChunks.EraseNonSorted(chunk - pool->fullChunks.Begin());
   }

   // check whether we need to free empty chunks
   const int emptyItems = pool->itemsPerChunk * pool->chunks.Length() - pool->allocated;

   if (4 * emptyItems > 5 * pool->itemsPerChunk) { // leave at least 1/4 empty elements
      for (int k = 0; k < pool->chunks.Length(); ++k) {
         CHUNK & cur = pool->chunks[k];

         if (cur.empty != pool->itemsPerChunk) {
            continue;
         }
         
         _FreeChunk(cur);
         pool->chunks.EraseNonSorted(k);
         pool->empty -= pool->itemsPerChunk;
         break;
      }
   }

   STRONG_ASSERT2(pool->allocated >= 0 && pool->empty >= 0, pool->allocated, pool->empty);

   pool->PrepareNextChunk();
}

/******************************************************************************/
/* ds::FIXED_SIZE_ALLOCATOR::_AllocChunk
/*
/******************************************************************************/
FIXED_SIZE_ALLOCATOR::CHUNK * FIXED_SIZE_ALLOCATOR::_AllocChunk(POOL & pool)
{
   CHUNK chunk;
   chunk.empty = pool.itemsPerChunk;
   chunk.data  = osAllocPage();

   STRONG_ASSERT1(sizeof(ITEM) <= pool.itemSize, pool.itemSize);

   ITEM * nextItem = NULL;
   for (int k = pool.itemsPerChunk - 1; k >= 0; --k) {
      ITEM * cur = (ITEM *)(chunk.data + pool.itemSize * k);
      cur->next = nextItem;
      nextItem = cur;
   }

   chunk.freeItem = nextItem;

   pool.chunks += chunk;
   return &pool.chunks.Back();
}

/******************************************************************************/
/* ds::FIXED_SIZE_ALLOCATOR::_FreeChunk
/*
/******************************************************************************/
void FIXED_SIZE_ALLOCATOR::_FreeChunk(CHUNK & chunk)
{
   osFreePage(chunk.data);

   chunk.data        = NULL;
   chunk.freeItem    = NULL;
   chunk.empty       = 0;
}

} // namespace ds